//
//  Problem1504.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/8.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1504. 统计全 1 子矩形 【动态规划】【1的矩形】
 给你一个只包含 0 和 1 的 rows * columns 矩阵 mat ，请你返回有多少个 子矩形 的元素全部都是 1 。

 示例 1：
     输入：mat = [[1,0,1],
                 [1,1,0],
                 [1,1,0]]
     输出：13
     解释：
     有 6 个 1x1 的矩形。
     有 2 个 1x2 的矩形。
     有 3 个 2x1 的矩形。
     有 1 个 2x2 的矩形。
     有 1 个 3x1 的矩形。
     矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。
 示例 2：
     输入：mat = [[0,1,1,0],
                 [0,1,1,1],
                 [1,1,1,0]]
     输出：24
     解释：
     有 8 个 1x1 的子矩形。
     有 5 个 1x2 的子矩形。
     有 2 个 1x3 的子矩形。
     有 4 个 2x1 的子矩形。
     有 2 个 2x2 的子矩形。
     有 2 个 3x1 的子矩形。
     有 1 个 3x2 的子矩形。
     矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。
 示例 3：
     输入：mat = [[1,1,1,1,1,1]]
     输出：21
 示例 4：
     输入：mat = [[1,0,1],[0,1,0],[1,0,1]]
     输出：5

 提示：
     1 <= rows <= 150
     1 <= columns <= 150
     0 <= mat[i][j] <= 1
 */
@objcMembers class Problem1504: NSObject {
    func solution() {
        print(numSubmat([[1,0,1],
                         [1,1,0],
                         [1,1,0]]))
        
        print(numSubmat([[0,1,1,0],
                         [0,1,1,1],
                         [1,1,1,0]]))
    }
    
    /*
     动态规划：
     1: 创建一个二维数组 dp[m][n]
     2: dp[i][j]: 已(0,0)为左上角，(i,j)为右下角，存储的子矩形的个数
     3: dp[i][j] = 以下面的矩形为例，求(1, 2)的个数 => dp[1][2]
        1 1 1
        1 1 1
        3.1: 首先利用动态规划，求出除了以(i,j)为右下角的所有子矩形的个数
        那么 dp[1][2] = dp[1][1] + d[0][2] - dp[0][1], 因为前2个想加多加了一个公共的区域
        3.2 在求出(i, j)为右下角的所有子矩形的个数
            if mat[1][2] == 0   // 说明：没有符合的
                // break
            else mat[1][2] != 0 // 右下角 == 1
                按照例子
                最底下一排：
                (1,2)~(1~2)自身是一个子矩形
                (1,1)~(1~2)是一个子矩形
                (1,0)~(1~2)是一个子矩形
                总结：num = (1,2)左侧有几个连续1的个数
                最后第二排
                (0,2)~(1~2)     是一个子矩形
                (0,1)(0,2)
                (1,1)(1,2)      是一个子矩形
                (0,0)(0,1)(0,2)
                (1,0)(0,1)(0,2) 是一个子矩形
                总结: num = (0,2)左侧有几个连续1的个数，并且<=下面一层的连续1的个数，不然不能构成矩形
    4: 我们创建一个数组row[m][n]
        row[m][n]: 在m行，(m,n)左测的连续1的个数
     */
    func numSubmat(_ mat: [[Int]]) -> Int {
        var dp = Array(repeating: Array(repeating: -1, count: mat[0].count), count: mat.count)
        var row = Array(repeating: Array(repeating: -1, count: mat[0].count), count: mat.count)
        
        // 特例：
        dp[0][0] = mat[0][0]
        return numSubmatDP(mat, &dp, &row, mat.count-1, mat[0].count-1)
    }
    
    func numSubmatDP(_ mat: [[Int]], _ dp: inout [[Int]], _ row: inout [[Int]], _ i: Int, _ j: Int) -> Int {
        if i < 0 || j < 0 {
            return 0
        }
        if dp[i][j] != -1 {
            return dp[i][j]
        }
        
        // 1: 首先利用动态规划，求出除了以(i,j)为右下角的所有子矩形的个数
        // 那么 dp[i][j] = dp[i][j-1] + d[j-1][j] - dp[i-1][j-1], 因为前2个想加多加了一个公共的区域
        dp[i][j] = numSubmatDP(mat, &dp, &row, i, j-1) + numSubmatDP(mat, &dp, &row, i-1, j) - numSubmatDP(mat, &dp, &row, i-1, j-1)
        // 2: 在求出(i, j)为右下角的所有子矩形的个数
        if mat[i][j] == 0 {
            row[i][j] = 0
        } else {
            // 求出最后一行连续1的个数，作为最大边界
            var maxLeft = Int.max
            for k in (0...i).reversed() {
                let value = numSubmatRow(mat, &row, k, j)
                
                if value > 0 {
                    maxLeft = min(maxLeft, value)
                    dp[i][j] += maxLeft
                } else {            //
                    break
                }
            }
        }
        
        return dp[i][j]
    }
    
    func numSubmatRow(_ mat: [[Int]], _ row: inout [[Int]], _ i: Int, _ j: Int) -> Int {
        if j < 0 || i < 0 {              // 边界
            return 0
        }

        if row[i][j] != -1 {
            return row[i][j]
        }
        
        if mat[i][j] == 0 {
            row[i][j] = 0
        } else {
            row[i][j] = numSubmatRow(mat, &row, i, j-1) + 1
        }
        
        return row[i][j]
    }
}
